Montgomery multiplication is one of the fundamental operations used in cryptographic algorithms, such as RSA and Elliptic Curve Cryptosystems. The security of a cryptographic system which is based on the multiplication and subsequent factoring of large numbers is related to the size of the numbers employed, for example, the number of bits or digits in the number. However, while it is desirable to include a large number of bits in each of the operands, the speed of Montgomery multiplication of these numbers becomes significantly slower as the number of bits increases.
Accordingly, it would be desirable and useful to provide an improved way of implementing Montgomery multiplication.